本发明涉及一种基于802.16d改进的Mesh election方法,包括计算当前进行竞争的时隙;根据竞争时隙和邻居信息确定邻居节点;同符合条件的邻居节点进行Mesh election;保存竞争成功的信息并进行广播。本发明能够协调两跳内各节点的控制子帧消息MSH-NCFG和调度子帧消息MSH-DSCH的发送、避免碰撞。
1.一种基于802.16d改进的Meshxa0election竞争方法,其特征是,包括:根据当前的时隙计算下次发送竞争的时隙;此时的时隙值为绝对值,包含超帧在内;根据竞争时隙和邻居信息确定邻居节点,所述的邻居节点要根据当前的竞争时隙进行判断,至少要满足下面三个条件之一:1)邻居的下次发送时间的区间包含当前竞争时隙,2)邻居的下下次发送时间的可能区间包含当前竞争时隙,3)邻居的下次发送时间不清楚;同符合条件的邻居节点进行Meshxa0election,如果竞争成功,则分配当前的竞争时隙给本节点的控制消息,并向邻居广播此消息;如果竞争失败,则进行下一个时隙的竞争,重新寻找符合条件的邻居节点进行竞争,直到成功为止;保存竞争成功的信息并进行广播;为了实现两跳邻居范围内的所有节点的竞争,广播时调度消息中携带的参数的计算方法需调整和修改;所述的计算过程的调整和修改,包括:下次发送时隙所在的区间范围不能基于当前的时隙得到,而是重新设定时间基准,以此基准为重新计算下次发送是假的区间范围;基准点设为处于时间长度为2^Exp的整数倍位置且与当前时间最为接近的点,Exp为标准中定义的退避指数值;发送节点发送Meshxa0election竞争结果时,根据基准和802.16d中给出的公式(1)得到调度消息中需携带的参数Mx和Exp;中间节点在转发邻居信息时,要根据当前的基准和公式(1)重新计算发送节点的调度参数Mx和Exp;两跳节点在收到信息后根据当前的基准和接收到的两个参数准确得出竞争结果的区间;
2^{XmtHoldoffExponent}·NextXmtMxXmtHoldoffExponent·(NextXmtMx+1)xa0xa0xa0xa0xa0xa0xa0xa0(1)。
2.根据权利要求1所述的基于802.16d改进的Meshxa0election竞争方法,其特征是,还进一步包括未入网节点的处理:Meshxa0election竞争时需要知道两跳邻居的调度信息,入网节点的邻居调度信息保存在其邻居链表中,未入网节点还未建立起邻居链表,需把信息保存在潜在邻居链表中,节点入网后首次确定节点的控制信息发送时间,需根据潜在邻居链表中的邻居调度信息进行Meshxa0election时隙竞争。
3.根据权利要求1所述的基于802.16d改进的Meshxa0election竞争方法,其特征是,还进一步包括本地信息的维护,具体内容包括:本地信息的维护包括网络描述消息(MSH-NCFG)下次发送时间的维护和分布式调度消息(MSH-DSCH)下次发送时间的维护,节点每次发送MSH-NCFG消息时,需通过竞争计算出MSH-NCFG下次发送的时间,并且对于每一个竞争成功的时隙都有对应的消息发送;但对于调度消息MSH-DSCH,对于每一个竞争成功的时隙不确定是否有调度消息发送,要保证Meshxa0election竞争的准确性,需保证每个竞争成功的时隙都有对应的调度消息发送;当调度消息的队列为空时,可以在此竞争成功的时隙内发送只携带本地调度信息和邻居调度信息的DSCH消息。技术领域
本发明涉及一种Meshxa0election(Mesh网竞争)方法,特别是涉及一种基于802.16d改进的Meshxa0election竞争方法,应用于无线自组网通信领域。
背景技术
IEEExa0802.16Mesh模式结构的基本思想是把信道分成控制和数据段,在控制子帧中,接入采用自由竞争机制;而数据子帧部分,通过控制子帧中消息的调度来避免碰撞。其中协议中规定控制子帧的时隙不是完全自由竞争的,每个节点通过随机选择算法争夺发送机会。Mesh模式下有两种调度数据的机制:集中式调度(Centralizedxa0Scheduling)和分布式调度(Distributedxa0Scheduling)。在分布式调度中,每个节点根据两跳邻居范围内的调度信息使用伪随机算法竞争信道接入,分布式调度可以更加自由和有效的建立连接并传送数据。分布式调度模式又分为两种,协调分布式调度模式和非协调分布式调度模式。两者的区别在于协调调度模式发送MSC-DSCH消息时是在控制子帧,而非协调调度模式是在数据子帧。IEEExa0802.16Mesh模式中协调分布式调度期望网络中不发生碰撞冲突,这样在一个节点的两跳邻居范围之内只有一个节点在一个控制时隙中发送数据。为了实现两跳范围内的控制子帧消息的竞争,802.16d协议提出了一种Meshxa0election算法。它是一个伪随机函数,需要输入时隙数量和节点的ID,其具体的算法过程在协议中有详细的描述。在输入参数的基础上算法产生一系列的伪随机值,在标准中这些值被称为混合值。如果当前的节点ID和时隙数产生一个最大的混合值,它就赢得竞争。否则,节点竞争不成功。如果节点赢了,设置暂时的传输时隙为它的下次传输时隙,然后在MSH-DSCH消息中广播此信息到邻居节点。如果节点失败,他将选择下次的传输时隙,然后重复上面的竞争行为直到成功。基于上面的描述,可以看出一个节点竞争成功的概率取决于总的竞争节点数目。而竞争节点数目与邻居节点的数目和拓扑结构有关。802.16d协议中给出Mesh模式下竞争信道的伪随机算法,同时为了节省网络资源,给出了两个参数Xmtxa0HoldoffExponent和Nextxa0Xmtxa0Mx表示竞争结果的区间。竞争的范围是两跳邻居范围内的所有节点,因此每个节点都需要知道两跳邻居范围内的所有节点的调度信息。802.16d协议中提到可以根据邻居的邻居调度信息获得两跳节点的调度信息,但是遵从协议中提出的下次发送时间的计算方法,接收节点无法准确获取两跳邻居的信息。要实现维护两跳邻居内的Meshxa0election竞争,必须设计一种新的维护两跳邻居的方法,来协调两跳内各节点的控制子帧消息的发送,避免碰撞。此外,大多文献涉及到Meshxa0election时,描述两跳邻居信息的获取是根据邻居广播的邻居调度信息,但并未给出具体的实施策略。少数提出了解决方案,可是概念很模糊,具体实施上也不明确。另外,关于未入网节点的处理和首次入网后如何确定控制消息的发送时间,在文献中也并未发现。因此,有必要提出一种改进的meshxa0election竞争方法。
发明内容
本发明在于避免以上现有技术的不足提出一种基于802.16d改进的Meshelection方法,用于协调两跳内各节点的控制子帧消息MSH-NCFG和调度子帧消息MSH-DSCH的发送,避免碰撞。本发明的技术方案为:一种基于802.16d改进的Meshxa0election竞争方法,其特征是,包括:根据当前的时隙计算下次发送竞争的时隙;此时的时隙值为绝对值,包含超帧在内;根据竞争时隙和邻居信息确定邻居节点,所述的邻居节点要根据当前的竞争时隙进行判断,至少要满足下面三个条件之一:1)邻居的下次发送时间的区间包含当前竞争时隙,2)邻居的下下次发送时间的可能区间包含当前竞争时隙,3)邻居的下次发送时间不清楚;同符合条件的邻居节点进行Meshxa0election,如果竞争成功,则分配当前的竞争时隙给本节点的控制消息,并向邻居广播此消息;如果竞争失败,则进行下一个时隙的竞争,重新寻找符合条件的邻居节点进行竞争,直到成功为止;保存竞争成功的信息并进行广播;为了实现两跳邻居范围内的所有节点的竞争,广播时调度消息中携带的参数的计算方法需调整和修改;所述的计算过程的调整和修改,包括:下次发送时隙所在的区间范围不能基于当前的时隙得到,而是重新设定时间基准,以此基准为重新计算下次发送是假的区间范围。基准点设为处于时间长度为2^Exp的整数倍位置且与当前时间最为接近的点,Exp为标准中定义的退避指数值。发送节点发送Meshxa0election竞争结果时,根据基准和802.16d中给出的公式(1)得到调度消息中需携带的参数Mx和Exp;中间节点在转发邻居信息时,要根据当前的基准和公式(1)重新计算发送节点的调度参数Mx和Exp;两跳节点在收到信息后根据当前的基准和接收到的两个参数准确得出竞争结果的区间。2^{Xmtxa0Holdoffxa0Exponent}·NextXmtMxXmtxa0HoldoffExponent·(NextXmtMx+1)xa0xa0xa0xa0(1)本发明还进一步包括未入网节点的处理:Meshxa0election竞争时需要知道两跳邻居的调度信息,入网节点的邻居调度信息保存在其邻居链表中,未入网节点还未建立起邻居链表,需把信息保存在潜在邻居链表中,节点入网后首次确定节点的控制信息发送时间,需根据潜在邻居链表中的邻居调度信息进行Meshxa0election时隙竞争。本发明还进一步包括本地信息的维护,具体内容包括:本地信息的维护包括网络描述消息(MSH-NCFG)下次发送时间的维护和分布式调度消息(MSH-DSCH)下次发送时间的维护,节点每次发送MSH-NCFG消息时,需通过竞争计算出MSH-NCFG下次发送的时间,并且对于每一个竞争成功的时隙都有对应的消息发送;但对于调度消息MSH-DSCH,对于每一个竞争成功的时隙不确定是否有调度消息发送,要保证Meshxa0election竞争的准确性,需保证每个竞争成功的时隙都有对应的调度消息发送;当调度消息的队列为空时,可以在此竞争成功的时隙内发送只携带本地调度信息和邻居调度信息的DSCH消息。本发明解决了802.16d对meshxa0election参数和过程定义不清楚的问题,实现两跳内各节点控制子帧消息的发送时隙竞争,避免碰撞。
附图说明
图1是参与竞争的邻居节点应符合的条件示意图;图2是Meshxa0election竞争流程图;图3是Meshxa0election中获取两跳邻居信息的流程图;
具体实施方式
本发明分析802.16d协议提出的MSH-NCFG和MSH-DSCH发送时间的竞争算法,提出一种切实可行的能够实现两跳范围内所有节点竞争的伪随机算法。基于802.16d设计的计算方法,包括改进竞争过程中计算方法,未入网节点的处理和本地信息的维护。基于802.16d设计的计算方法是基于802.16d协议的分布式调度Mesh网所设计的一种计算方法,其基本思想是根据协议的规定进行设计,中心部分如竞争过程中的随机算法,就是采用协议中提供的伪随机算法。但同时对协议中一些不明确的部分进行了修改和补充,例如协议中并未准确提出如何维护两跳邻居的信息。所述的改进竞争过程中计算的方法具体内容包括:在竞争的实现中,为了节省网络资源,802.16d协议规定节点在广播参数时并不直接发送其Meshelection竞争结果,而是只发送其竞争结果的区间。802.16d协议定义了两个参数Xmtxa0Holdoffxa0Exponent和Nextxa0Xmtxa0Mx用以表示这个区间,如公式(1)所示。公式中Nextxa0Xmtxa0Time的区间范围是基于当前的时隙得到的。但遵从此种算法,范围为两跳的邻居无法准确获取本地节点调度消息中的信息。邻居节点是根据当前时间计算得到本地节点的Meshxa0election结果。如果不清楚本地节点的发送时间,邻居节点就无法准确计算出Meshxa0election竞争结果。因此,两跳邻居要获得发送节点的信息,必须经过中间节点的转化。怎样转化才能使得信息不丢失,是维护两跳邻居的算法核心。为了维护信息的准确性,参数的计算过程需调整和修改。计算过程的调整和修改,其基本思想是Nextxa0Xmtxa0Time的区间范围是不能基于当前的时隙得到,而是根据当前的时隙重新设计时间基准,以此时间基准重新计算下次发送时间的区间范围。所有节点都明确基准的算法。基准点设为时间长度为2的整数倍位置的点,其大小还需根据Meshxa0election过程和当前的网络状态等条件进行调整,方法灵活。发送节点发送Meshxa0election竞争结果时,根据基准和公式(1)得到调度消息中需携带的参数Mx和Exp。中间节点在转发邻居信息时,要根据当前的基准和公式(1)重新计算发送节点的调度参数Mx和Exp。两跳节点在收到信息后根据当前的基准和接收到的两个参数准确得出竞争结果的区间。所述的未入网节点的处理具体内容包括:802.16d并未说明未入网节点的处理。Meshxa0election竞争时需要知道两跳邻居的调度信息,入网节点的邻居调度信息保存在其邻居链表中,未入网节点还未建立起邻居链表,只能把信息保存在潜在邻居链表中,节点入网后首次确定节点的控制信息发送时间,就是根据潜在邻居链表中的邻居调度信息进行Meshxa0election时隙竞争。如此处理,可以避免首次控制消息的碰撞,同时避免恶性循环。因为首次控制消息可以向邻居广播信息,告知邻居它的存在,邻居可以在竞争过程中将此节点作为可能的竞争对象。如果首次控制消息发送失败,邻居无法获得它的信息,认为此节点不存在,由此可能会造成恶性循环。所述的本地信息的维护具体内容包括:本地信息的维护包括MSH-NCFG下次发送时间的维护和MSH-DSCH下次发送时间的维护。节点每次发送MSH-NCFG消息时,需要通过竞争计算出MSH-NCFG下次发送的时间,并且对于每一个竞争成功的时隙都有对应的消息发送。但对于调度消息MSH-DSCH,对于每一个竞争成功的时隙不确定是否有调度消息发送。要保证Meshxa0election竞争的准确性,需保证每个竞争成功的时隙都有对应的调度消息发送。当调度消息的队列为空时,可以在此竞争成功的时隙内发送只携带本地调度信息和邻居调度信息的DSCH消息。其目的就是维护本地和邻居信息。以下结合附图2对本发明的实施流程做进一步说明。(1)确定符合竞争条件的邻居节点不是所有的两跳范围内的邻居节点都要参与竞争,竞争的邻居节点要根据当前的竞争时隙进行判断,至少要满足下面三个条件之一,如图1所示:邻居的下次发送时间的区间包含当前竞争时隙,可能发送碰撞(节点B);邻居的下下次发送时间的可能区间(由于不清楚邻居的下下次发送时间的区间,只能是一个大概的范围)包含当前竞争时隙(节点C);邻居的下次发送时间不清楚(节点D)。(2)同符合条件的邻居节点进行Meshxa0election确定当前的竞争时隙,同时根据竞争时隙确定竞争节点后,开始进行竞争过程。竞争过程采用802.16d给出的伪随机算法,如果竞争成功,则分配当前的竞争时隙给本节点的控制消息,并向邻居广播此消息;如果竞争失败,则进行下一个时隙的竞争,重新寻找符合条件的邻居节点进行竞争,直到成功为止。(3)广播竞争结果如图3,假设A点竞争成功同时广播竞争结果,以此为例说明两跳邻居C如何获取节点的调度信息。A广播竞争结果前,首先需要根据竞争结果和公式(1)计算出Mx,Mx是竞争时隙所在区间的起始标识。要想B和C能准确获取这个区间,计算时不能以当前时间点1为基准,而是重新计算一个时间基准standardxa0point1,计算公式如下:ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="616"/>其中Currentxa0Xmtxa0Time为本次发送时间,HoldoffExpontent为节点A的退避指数。得到时间基准后,算出Mx,然后将表示区间的两个参数HoldoffExpontent和Mx发送出去。B接收到A发送的消息,根据接收到的时间和公式(3)计算得到B的时间基准standardxa0point1,此值应该和A的相等。根据standardxa0point1,B点就可以准确获取A点的调度消息所在的区间。B在2处发送消息时,会转发A的调度消息。转发时,B需要根据当前的时间重新计算时间基准standardxa0point2,并且要根据standardxa0point2重新计算两个参数。然后进行转发。C收到B转发的消息后,根据接收到的时间和公式(3)计算得到C的时间基准standardxa0point2,此值应该和B的相等。根据standardxa0point2,C点就可以准确获取A点的调度消息所在的区间。